package complexite;

import complexite.RandomQuickSelect;


public class QuickSelect {

	
	
	public static int bon_pivot(int nbbloc,ExtArrayList a){
		System.out.println("QuickSelect.bon_pivot()");
		
		ExtArrayList bloc ;
		ExtArrayList medmed = new ExtArrayList();
		
		
		int i;
		for( i=0; i<a.size()-nbbloc ;i+=nbbloc){	
			//on decoupe en block
			bloc=new ExtArrayList(a.subList(i,i+nbbloc));
//			System.out.println("block complet" + i);
			//on tri le block
			faireTriInsertion(bloc);
			//on recup la mediane du block et la rajoute dans medmed
			int med=bloc.get(bloc.size()/(bloc.size()/2));
			medmed.add(med);
		}
		
		//on traite le dernier cas a par
		bloc=new ExtArrayList(a.subList(i,a.size()));
		System.out.println("valeur de dernier bloc :"+bloc);
		faireTriInsertion(bloc);
		int med=bloc.get(((bloc.size() +1) / 2)-1);
		medmed.add(med);
		
		
//		System.out.println("valeur des médians :"+medmed);
		
		
		return Selection ( medmed,0, medmed.size() - 1, (medmed.size()+1)/2, nbbloc);
	}
	
	
	public static void faireTriInsertion(ExtArrayList az){
	    boolean bRetour = false;
	    int cpt;
	    int i;
	    int lg;
	    int Val;
	    lg = az.size();
	    
	    for(i = 1; i < lg ; i++)
	    {    
	        Val = az.get(i);
	        cpt = i-1;
	        do
	        {
	            bRetour = true;
	            if(az.get(cpt) > Val)
	          {    
	            	az.set(cpt+1,az.get(cpt));
	                cpt = cpt-1;
	                bRetour = false;
	            }
	            if(cpt <0)
	            {
	                bRetour = true;
	            }
	        }while(!bRetour);
	        az.set(cpt+1,Val);     
	    }
	}

	
	public static int Selection (ExtArrayList a,int p, int r,int i, int nbbloc){
		System.out.println("QuickSelect.Selection()");
		System.out.println("p:" + p + "  r:" + r + " i:" + i);
		if(p==r){
			System.out.println("pivot " + a.get(p));
			return a.get(p);
		}
		System.out.println("petit truc a la con, on sait jamais, c'est bio");
		// recherche random : int piv= p + new Random().nextInt((r - p) + 1);
		int piv = bon_pivot(nbbloc,a);
		System.out.println("avant partitionR");
		System.out.println("p:" + p + "  r:" + r + " piv:" + piv);
		int q = Partitionner(a,p,r,piv);
		System.out.println("		fin" + a);
		System.out.println("après partitionR");
		int k=q-p+1;
		
		if(i<=k)
			return Selection(a, p, q, i,nbbloc);
		else
			return Selection(a, q+1, r, i-k,nbbloc);
		
	}
	
	//
	public static int Partitionner (ExtArrayList a, int gauche,int droite,int piv){
		int i = gauche - 1;
		int j = droite + 1;
		System.out.println("		QuickSelect.Partitionner()");
		System.out.println("		pivot : " + piv);
		System.out.println("		deb" + a);
		while(true){
			do{
				j--;
			}
			while(a.get(j) > piv);
			
			do{
				i++;
			}
			while(a.get(i) < piv);
			
			if(i < j)
				RandomQuickSelect.echange(a,i,j);
			else{
				System.out.println("[" + gauche + " " + j + "]" + "   " + "[" + (j+1) + " " + droite + "]" );
				return j;
			}	
		}
	}
	
	
//	public static void main(String[] args) {
//		ExtArrayList az = new ExtArrayList();
//		az.getArray(5, 10, 30);
//		System.out.println("pas trié: " +az);
//		//System.out.println(Selection(az , 0 , az.size()-1 , (az.size()+1)/2 , 5));
//		//System.out.println("trié: " + az);
//		Partitionner(az, 0, az.size() - 1, az.get(0));
//		System.out.println("part: " + az);
//		
//		
//	}
}
